package com.kingwood.algorithm.test200;

import javafx.scene.layout.Priority;

import java.util.*;

// 可以处理的最大任务数
// https://fcqian.blog.csdn.net/article/details/135005316
public class MaxTask {
    static class Task {
        int start;
        int end;
        public Task(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static int getResult(int[][] taskArr, int n) {
        PriorityQueue<Task> pq = new PriorityQueue<>((a, b) -> a.end != b.end ? b.end - a.end : b.start - a.start);

        for (int i=0; i<n; i++) {
            int start = taskArr[i][0];
            int end = taskArr[i][1];

            pq.offer(new Task(start, end));
        }

        int count = 0;
        int last_end = Integer.MAX_VALUE;

        while (pq.size() > 0) {
            Task task = pq.poll();
            if (task.end < last_end) {
                last_end = task.end;
                count++;
            } else if (last_end > task.start){
                task.end = last_end - 1;
                pq.offer(task);
            }
        }

        return count;
    }

    public static int getResult2(int[][] taskArr, int n) {
        Arrays.sort(taskArr, (a, b) -> b[1] - a[1] );
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b -a);

        int pq_end = Integer.MAX_VALUE;
        int count = 0;

        for (int[] task : taskArr) {
            int start = task[0];
            int end = task[1];

            while (pq.size() > 0 && pq_end > end) {
                if (pq_end >= pq.poll()) {
                    // 如果任务开始时间未超过结束时间，则可以执行
                    count++;
                    pq_end--;
                }
            }

            pq.add(start);
            pq_end = end;
        }

        while (pq.size() > 0) {
            if (pq_end >= pq.poll()) {
                count++;
                pq_end--;
            }
        }

        return count;
    }


    public static int getResult3(int[][] taskArr, int n) {
        List<Task> taskList = new ArrayList<>();
        for (int i=0; i<n; i++) {
            int start = taskArr[i][0];
            int end = taskArr[i][1];

            taskList.add(new Task(start, end));
        }
        // n = 5
        // [{1,3},{2,3},{3,4},{3,5},{4,5}]
        taskList.sort((a, b) -> a.end != b.end ? a.end - b.end : a.start - b.start);
        int count = 0;
        int curEnd = taskList.get(n-1).end;

        for (int i=n-1; i>=0; i--) {
            Task task = taskList.get(i);
            if (task.start <= curEnd) {
                count++;
                curEnd--;
            }

            if (task.end < curEnd) {
                curEnd = task.end;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] taskArr = new int[n][2];

        for (int i=0; i<n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            taskArr[i][0] = start;
            taskArr[i][1] = end;
        }

        int ans1= getResult(taskArr, n);
        System.out.println(ans1);

        int ans2 = getResult2(taskArr, n);
        System.out.println(ans2);

        int ans3 = getResult3(taskArr, n);
        System.out.println(ans3);
    }
}
